package com.leetcode.根据数据结构分类.数组;

import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * @author: ZhouBert
 * @date: 2021/2/1
 * @description: 1438. 绝对差不超过限制的最长连续子数组
 * https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/
 */
public class B_1438_绝对差不超过限制的最长连续子数组 {

	public static void main(String[] args) {
		int[] nums = new int[]{8, 2, 4, 7};
//		nums = new int[]{10, 1, 2, 4, 7, 2};
		nums = new int[]{4, 2, 2, 2, 4, 4, 2, 2};
		int limit = 4;
//		limit = 5;
		limit = 0;
		B_1438_绝对差不超过限制的最长连续子数组 action = new B_1438_绝对差不超过限制的最长连续子数组();
		int res = action.longestSubarray(nums, limit);
		res = action.longestSubarrayByDequee(nums, limit);
		System.out.println("res = " + res);
	}

	/**
	 * 可以通过双指针 + 剪枝的方法进行判断
	 * 由于求的是【连续子数组】的长度，所以小于已知的最长长度可以忽略。
	 *
	 * @param nums
	 * @param limit
	 * @return
	 */
	public int longestSubarray(int[] nums, int limit) {
		int res = 1;
		int len = nums.length;

		int begin = 0, end = 1;
		//min 和 max 是动态的，考虑用 Heap 进行辅助
		int min = nums[0], max = min;
		PriorityQueue<Integer> bigTopHeap = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o2 - o1;
			}
		});
		bigTopHeap.offer(max);
		PriorityQueue<Integer> smallTopHeap = new PriorityQueue<>();
		smallTopHeap.offer(min);
		while (end < len) {
			bigTopHeap.offer(nums[end]);
			smallTopHeap.offer(nums[end]);
			max = bigTopHeap.peek();
			min = smallTopHeap.peek();
			if (max - min > limit) {
				//到达本次的极限
				smallTopHeap.remove(nums[begin]);
				bigTopHeap.remove(nums[begin]);
				begin++;
			}
			end++;
			res = Math.max(end - begin, res);
		}

		return res;
	}


	/**
	 * 通过 两个 Deque 实现
	 *
	 * @param nums
	 * @param limit
	 * @return
	 */
	public int longestSubarrayByDequee(int[] nums, int limit) {
		//这里维护的是最大值们对应的下标
		Deque<Integer> maxQ = new LinkedList<>();
		Deque<Integer> minQ = new LinkedList<>();
		int ans = 0;
		//窗口左沿
		int start = 0;
		//窗口右沿
		for (int end = 0; end < nums.length; end++) {
			//右沿元素进入窗口、维护最大值单调队列
			while (!maxQ.isEmpty() && nums[maxQ.peekLast()] < nums[end]) {
				maxQ.pollLast();
			}
			maxQ.add(end);
			//右沿元素进入窗口、维护最小值单调队列
			while (!minQ.isEmpty() && nums[minQ.peekLast()] > nums[end]) {
				minQ.pollLast();
			}
			minQ.add(end);

			//如果当前窗口的最大值最小值的差大于 limit，则不断缩小窗口（左沿++），直至最大值变小或者最小值变大从而满足 limit 限制
			while (!maxQ.isEmpty() && !minQ.isEmpty() && nums[maxQ.peek()] - nums[minQ.peek()] > limit) {
				if (maxQ.peek() <= start) maxQ.poll();
				if (minQ.peek() <= start) minQ.poll();
				start++;
			}
			ans = Math.max(ans, end - start + 1);
		}
		return ans;
	}

}
